Data storage involves the recording of digital computer data in a machine-readable medium. Storage generally refers to the retention of data over relatively longer periods of time than the typical retention of data in computer memory. Data storage media includes, for example, magnetic tape, hard disk drive (HDD), optical disk, flash memory and solid-state drive (SSD) devices.
Erasure coding (EC) typically refers to a method of securing stored data in which the data is broken into fragments, or chunks, which are expanded through an encoding process into codewords that include redundant data pieces, or symbols. The codewords generally are individually stored across multiple distributed storage media locations, or nodes. In general, when one or more nodes are erased or fail, the symbols stored in more than one of the remaining nodes can be used to reconstruct the data that was stored in the erased or failed node(s).
In general, erasure coding can provide greater fault tolerance than data replication methods with respect to the required amount of storage space, or storage overhead, in a distributed storage system. However, compared to replication, erasure codes typically require more network traffic and more input/output (I/O) accesses to the storage media in order to rebuild, or repair, lost data.
Regenerating codes include erasure codes that allow for rebuilding a failed node by accessing a subset of stored symbols on a subset of the remaining nodes such that the amount of network traffic required to repair the failed node is less that the complete data set. Ideally, regenerating codes provide a theoretically optimal tradeoff between the amount of data stored at each storage node, or storage overhead, and the network traffic, or repair bandwidth, required to regenerate the lost data.
The two extrema of this theoretically optimal tradeoff are known as Minimum Storage Regenerating (MSR) codes, which minimize the required storage node size at the expense of required repair bandwidth, and Minimum Bandwidth Regenerating (MBR) codes, which minimize the required repair bandwidth at the expense of required storage node size.
Exact Regenerating codes include Regenerating codes that allow for rebuilding of the exact content that was stored on a failed storage node. Further, exact regenerating codes, which precisely reconstruct storage data, cannot be achieved between the MSR and MBR points.
Several constructions of exact regenerating codes have been presented that attain the optimal tradeoff. MBR codes have been developed for any number of storage nodes having fault tolerances of any number less than the total number of storage nodes.
Nevertheless, some of the constructions of MSR code require that the data be fragmented into relatively small chunks before every encoding, decoding or repair operation. The required chunk size becomes exponentially smaller with respect to an increase in the number of nodes used to store the data. This factor can add complexity and cost to the storage process, making these MSR codes impractical for some storage scenarios.